package sort;

import javafx.scene.input.DataFormat;

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * Created by IntelliJ IDEA.
 * User: 杰哥
 * Date: 2020/4/4
 * Time: 21:37
 */
public class BubbleSort {

    public static void main(String[] args) {
        int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
//        int arr[] = new int[1000];
//        for (int i = 0; i < 1000; i++) {
//            arr[i] = (int)(Math.random() * 1000);
//        }
        Date date1 = new Date();
        testSort(arr);
        Date date2 = new Date();
        System.out.println("用是：" + (date2.getTime() - date1.getTime()) + "毫秒" );
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 冒泡排序
     * 交换排序的一种
     * 时间复杂度 O(n^2)
     */
    public static void bubbleSort(int[] arr) {
        int temp = 0;
        boolean flag = true;
        for (int i = 0; i < arr.length - 1; i++) {
            flag = true;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = false;
                }
            }
            if(flag) { //循环对比一遍没有交换位置说明数组排序已经完毕，提前结束循环
                break;
            }
        }
    }

    /**
     * 选择排序
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            //记录最小值
            int min = arr[i];
            //记录最小值所在下标
            int minIndex = i;
            for (int j = 1 + i; j < arr.length; j++) {
                if(arr[j] < min) {
                    min = arr[j];
                    minIndex = j;
                }
            }
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
        /**
         * 思路：
         * 第一次：找出数组里最小的一个数放在第一个，
         * 第二次: 找出数组里（排除数组前一个数）最小的一个数放在第二个
         * 第三次: 找出数组里（排除数组前两个数）最小的一个数放在第三个
         * ......
         */
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] arr) {
        //  记录当前要插入的值
        int insertVal = 0;
        //  记录当前要插入的值的前一个值的下标
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //退出循环时，说明 insertVal 已经比数组 arr[insertIndex] 大且比数组 arr[insertIndex+1] 小，或比前面的都要小
            arr[insertIndex + 1] = insertVal;
        }
    }

    public static void testSort(int[] arr) {
        int temp = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = i -1; j >= 0; j -= 1) {
                if(arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

}
